AM-GM Inequality
Theorem
The generalised AM-GM inequality states that for \(x_{1}, x_{2}, \dots, x_{n} \geq 0\):
\[ (x_{1}\cdot \dots \cdot x_{n})^{\frac{1}{n}} \leq \frac{1}{n} \sum_{k = 1}^{n} x_{k}.\]
That is, the arithmetic mean is greater than or equal to the geometric mean.
Proof Using Jensen's Inequality
The AM-GM inequality can be proven quite simply by applying Jensen's inequality with \(a_{i} = \frac{1}{n}\) and \(f = -\ln\). Written out explicitly this means:
\[-\ln\left(\sum_{i = 1}^{n} \frac{1}{n} x_{i}\right) \leq \sum_{i = 1}^{n} \frac{1}{n} (-\ln(x_{i})).\]
The by negating both sides, and applying the exponential function, we have:
\[\begin{align*}
& \ln\left(\sum_{i = 1}^{n} \frac{1}{n} x_{i}\right) \geq \sum_{i = 1}^{n} \frac{1}{n} \ln(x_{i}) \\
& \implies \sum_{i = 1}^{n} \frac{1}{n} x_{i} \geq \exp\left(\sum_{i = 1}^{n} \frac{1}{n} \ln(x_{i})\right) \\
& \implies \sum_{i = 1}^{n} \frac{1}{n} x_{i} \geq \exp\left(\sum_{i = 1}^{n} \ln(x_{i}^{\frac{1}{n}})\right) \\
& \implies \sum_{i = 1}^{n} \frac{1}{n} x_{i} \geq \prod_{i = 1}^{n} x_{i}^{\frac{1}{n}} \\
& \implies \sum_{i = 1}^{n} \frac{1}{n} x_{i} \geq \left(\prod_{i = 1}^{n} x_{i}\right)^{\frac{1}{n}}. \\
\end{align*}\]
Proof Using Cauchy Induction
The above proof depends on the convexity \(-\ln\). It is however possible to prove it more directly without the need for this fact and Jensen's inequality. This proof uses Cauchy induction.
Base Case
We first prove a base case when \(n = 2\):
\[\begin{align*}
0 &\leq (\sqrt{a} - \sqrt{b})^{2} \\
0 &\leq a - 2\sqrt{ab} + b \\
2\sqrt{ab} &\leq a + b \\
\sqrt{ab} &\leq \frac{a + b}{2} \\
\end{align*}\]
\(S(n) \implies S(2n)\) for \(n \geq 1\)
We assume that the AM-GM inequality is true for \(n\) terms, and then proceed by considering the arithmetic mean of \(2n\) terms:
\[\begin{align*}
\frac{1}{2n} \sum_{k = 1}^{2n} x_{k} &= \frac{\frac{1}{n} \sum_{k = 1}^{n} x_{k} + \frac{1}{n} \sum_{k = n + 1}^{2n} x_{k}}{2} \\
&\geq \frac{\left(\prod_{k = 1}^{n} x_{k}\right)^{\frac{1}{n}} + \left(\prod_{k = n + 1}^{2n} x_{k}\right)^{\frac{1}{n}}}{2} \\
&\geq \sqrt{\left(\prod_{k = 1}^{n} x_{k}\right)^{\frac{1}{n}} \cdot \left(\prod_{k = n + 1}^{2n} x_{k}\right)^{\frac{1}{n}}} \\
&= \sqrt{\left(\prod_{k = 1}^{2n} x_{k}\right)^{\frac{1}{n}} } \\
&= \left(\prod_{k = 1}^{2n} x_{k}\right)^{\frac{1}{2n}} \\
\end{align*}\]
\(S(n) \implies S(n - 1)\) for \(n \geq 2\)
Again we assume that the AM-GM inequality is true for \(n\) terms. To reduce the expression to \(n - 1\) terms, we let the \(n^{\text{th}}\) term be the arithmetic mean of the previous \(n - 1\), that is:
\[x_{n} = \frac{1}{n - 1} \sum_{k = 1}^{n - 1} x_{k}.\]
Then we have:
\[\begin{align*}
\left(\prod_{k = 1}^{n} x_{k} \right)^{\frac{1}{n}} &\leq \frac{1}{n} \sum_{k = 1}^{n} x_{k} \\
\left(\prod_{k = 1}^{n - 1} x_{k} \right)^{\frac{1}{n}} \times \left(x_{n}\right)^{\frac{1}{n}} &\leq \frac{1}{n} \sum_{k = 1}^{n - 1} x_{k} + \frac{1}{n}x_{n} \\
\left(\prod_{k = 1}^{n - 1} x_{k} \right)^{\frac{1}{n}} \times \left(\frac{1}{n - 1} \sum_{k = 1}^{n - 1} x_{k} \right)^{\frac{1}{n}} &\leq \frac{1}{n} \sum_{k = 1}^{n - 1} x_{k} + \frac{1}{n(n - 1)} \sum_{k = 1}^{n - 1} x_{k} \\
\left(\prod_{k = 1}^{n - 1} x_{k} \right)^{\frac{1}{n}} \times \left(\frac{1}{n - 1} \sum_{k = 1}^{n - 1} x_{k} \right)^{\frac{1}{n}} &\leq \left(\frac{1}{n} + \frac{1}{n(n - 1)}\right) \sum_{k = 1}^{n - 1} x_{k} \\
\left(\prod_{k = 1}^{n - 1} x_{k} \right)^{\frac{1}{n}} \times \left(\frac{1}{n - 1} \sum_{k = 1}^{n - 1} x_{k} \right)^{\frac{1}{n}} &\leq \frac{1}{n - 1} \sum_{k = 1}^{n - 1} x_{k} \\
\left(\prod_{k = 1}^{n - 1} x_{k} \right)^{\frac{1}{n}} &\leq \frac{\frac{1}{n - 1} \sum_{k = 1}^{n - 1} x_{k}}{\left(\frac{1}{n - 1} \sum_{k = 1}^{n - 1} x_{k} \right)^{\frac{1}{n}}} \\
\left(\prod_{k = 1}^{n - 1} x_{k} \right)^{\frac{1}{n}} &\leq \left(\frac{1}{n - 1} \sum_{k = 1}^{n - 1} x_{k}\right)^{\frac{n - 1}{n}} \\
\left(\prod_{k = 1}^{n - 1} x_{k} \right)^{\frac{1}{n - 1}} &\leq \frac{1}{n - 1} \sum_{k = 1}^{n - 1} x_{k}. \\
\end{align*}\]
